﻿using System;
using System.Collections.Generic;
namespace Hanoi
{
    /// <summary>
    /// 汉诺塔问题
    /// </summary>
    class Program
    {
        static int count = 0;
        static void Main(string[] args)
        {
            Console.WriteLine("请输入盘数：");
            int n = Convert.ToInt32(Console.ReadLine());
            HanNuo(n, 'A', 'B', 'C');
            Console.WriteLine($"一共需要{count}步");      //计算移动次数
            Console.ReadKey();
        }
        static void HanNuo(int n, char A, char B, char C)
        {
           
            if (n==1)                                     //也是递归终止条件
            {
                Console.WriteLine($"圆盘{n}号从{A}=>{C}");//n=1时，直接从A柱到C柱上
                count++;
            }
            else
            {
                HanNuo(n - 1, A, C, B);                   //将A柱上从上到下n-1个盘移动到B柱上
                Console.WriteLine($"圆盘{n}号从{A}=>{C}");
                count++;
                HanNuo(n - 1, B, A, C);                   //将B柱上的n-1个盘子移到C柱上
            }
           
        }
    }
}
